//图的遍历
//定义：从已给的【连通图】某一顶点触发，沿着一些边遍历图中的所有顶点，且每个顶点仅【被访问一次】。
//遍历实质：找每个顶点的邻接点的过程

//图的特点：
//图中可能存在回路，且图的任一顶点都可能与其他顶点相同，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
//如何避免重复访问？
//解决思路：设置辅助数组【visited[n]】，用来标记某个被访问过的顶点。当顶点i被访问，改visited[i]为1，防止多次被访问

//图遍历的常用方法
//DFS(Depth_First Search)深度优先搜索
//BFS(Breadth_Frist Search)广度优先搜索

//【稠密图】适于【邻接矩阵】上进行【深度遍历DFS】
//【稀疏图】适于【邻接表】进【深度遍历DFS】

//非连通图使用辅助栈来遍历，通过栈空状态次数来判断有几个连通分量

//【DFS 】【邻接矩阵】遍历
using _6.图;

var g = new 邻接矩阵表示法.AMGraph(
	['1', '2', '3', '4', '5', '6'],
	[
			[0,1,1,1,0,0],
			[1,0,0,0,1,0],
			[1,0,0,0,1,0],
			[1,0,0,0,0,1],
			[0,1,1,0,0,0],
			[0,0,0,1,0,0]
		]);

//g.DFS(1);
//g.DFS2(1);
//g.BFS(1);



//有向无环图（DAG）及其应用

//AOV网：用一个有向图表示一个工程的各个【子工程及其相互制约的关系】，
//其中以【顶点表示活动】，【弧表示活动之间】的【优先制约关系】。
//这种有向图称为【顶点表示活动的网】简称AOV网

//AOE网：
//用一个有向图表示一个工程的各个【子工程及其相互制约的关系】，
//其中以【弧表示活动】，【点表示活动】的【开始或结束事件】。
//这种有向图称为【边表示活动的网】简称AOE网

//拓扑排序应用：
//安排课表：由于有些课程需要有前置课程，可以确定课程学习顺序
//构建系统：确定模块或者文件的编译顺序
//任务调度：某些任务之间存在依赖关系，可以确定执行顺序


//拓扑排序方法：
//1.在有向图选一个没有前驱的顶点且输出之，
//2.从图中删除该顶点和所有以它为尾的弧。
//重复1，2直到【全部顶点输出】或者【不存在无前驱的顶点】为止
//最终若顶点全部输出则输出的顶点序列为拓扑序列，序列不是不唯一的
//若序列中存在图中所有顶点则必不存在环	


//拓扑排序前提，不存在环
//先进行环检测，通过在进行排序得出拓扑排序序列


//构建有向图，使用邻接表的方式
var vertices = new VertexNode[6]
{
	new(){Data='A',Firstarc=null },
	new(){Data='B',Firstarc=new ArcNode{ AdjVex=0,Next=new ArcNode{AdjVex=3,Next=null } } },
	new(){Data='C',Firstarc=new ArcNode{ AdjVex=0,Next=new ArcNode{AdjVex=3,Next=null } }},
	new(){Data='D',Firstarc=new ArcNode{ AdjVex=0,Next=new ArcNode{AdjVex=5,Next=null } }},
	new(){Data='E',Firstarc=new ArcNode{ AdjVex=2,Next=new ArcNode{AdjVex=3,Next=new ArcNode{ AdjVex=5,Next=null } } }},
	new(){Data='F',Firstarc=null},
};


var vertices2 = new VertexNode[6]
{
    new(){Data='1',Firstarc=new ArcNode{ AdjVex=1,Next=new ArcNode{ AdjVex=2} } },
    new(){Data='2',Firstarc=new ArcNode{ AdjVex=2 } },
    new(){Data='3',Firstarc=new ArcNode{ AdjVex=3 }},
    new(){Data='4',Firstarc=new ArcNode{ AdjVex=4 }},
    new(){Data='5',Firstarc=new ArcNode{ AdjVex=5  }},
    new(){Data='6',Firstarc=null },
};

//Topo_Kahn(vertices2);
//Console.WriteLine("~~~~~~~~");
//Topo_DFS(vertices2);


//var f = new Solution()
//    .CanFinish(20, [[0, 10], [3, 18], [5, 5], [6, 11], [11, 14], [13, 1], [15, 1], [17, 4]]);
//var f2 = new Solution()
//    .CanFinish(2, [[1, 0]]);
//var f3 = new Solution()
//    .CanFinish(3, [[1, 0],[1,2],[0,1]]);
//Console.WriteLine(f);
//Console.WriteLine(f2);
//Console.WriteLine(f3);

var r = new Solution3()
    .CheckIfPrerequisite(4, [[2, 3], [2, 1], [0, 3], [0, 1]],
    [[0, 1], [0, 3], [2, 3], [3, 0], [2, 0], [0, 2]]);
Console.WriteLine(string.Join(',',r));
return;

//使用dfs来完成拓扑排序
void Topo_DFS(VertexNode[] vers)
{
    var topoStack = new Stack<int>(vers.Length);
    // 0 未搜索 1搜索中 2已完成
    var st = new int[vers.Length];

    for (int i = 0; i < vers.Length; i++)
    {
        if (st[i] == 0 && DFS(i) == false)
        {
            Console.WriteLine("存在环路无法进行拓扑排序");
            return;
        }
    }

    //输出拓扑序列，如果有的话
    Console.WriteLine("拓扑排序成功");
    while (topoStack.Count != 0)
    {
        Console.WriteLine(vers[topoStack.Pop()].Data);
    }


    bool DFS(int i)
    {
        //标记搜索中
        st[i] = 1;
        for (var p = vers[i].Firstarc; p!=null; p=p.Next)
        {
            //邻接点索引
            var j = p.AdjVex;
            //如果节点还未被访问，则进行递归访问s
            if (st[j] == 0)
            {
                if (DFS(j) == false)
                    return false;
            }
            else if (st[j] == 1)
                return false;
        }
        
        //入结果栈，并标记搜索完成
        topoStack.Push(i);
        st[i] = 2;
        return true;
    }

}


//使用Kahn方法进行拓扑排序
void Topo_Kahn(VertexNode[] vers)
{
    //idx:点序号 value:入度
    var inList = new int[vers.Length];
    //计算入度存储inList
    for (int i = 0; i < vers.Length; i++)
        for (var p = vers[i].Firstarc; p != null; p=p.Next)
            //记录入度+1
            inList[p.AdjVex]++;
    
    //初始化,将所有入读为0的点加入队列
    var queue = new Queue<VertexNode>();
    for (int i = 0; i < inList.Length; i++)
        if (inList[i] == 0)
            queue.Enqueue(vers[i]);

    //所有的点入度都不为0，说明一定有环
    if (queue.Count == 0)
    {
        Console.WriteLine("存在环，拓扑排序失败");
        return;
    }

    var sortResult = new List<char>();
    while (queue.Count != 0)
    {
        //取出入度为0的一个点
        var node = queue.Dequeue();
        //加入拓扑排序结果
        sortResult.Add(node.Data);
        //删除这个点的出边(相邻节点入度减1)
        for (var p = node.Firstarc; p != null;  p = p.Next)
        {
            inList[p.AdjVex]--;
            //若入度减到0则加入队列
            if (inList[p.AdjVex] == 0)
                queue.Enqueue(vers[p.AdjVex]);
        }
    }

    var ss = vers.Select(x => x.Data).ToList();
    if (sortResult.Intersect(ss).Count() == ss.Count)
    {
        Console.WriteLine("拓扑排序成功");
    }
    else
    {
        Console.WriteLine("存在环，拓扑排序失败");
    }
    Console.WriteLine(string.Join(",", sortResult));


}

//顶点表节点
public class VertexNode
{
	//这个点表示的内容
	public char Data;
	//第一个邻接点
	public ArcNode Firstarc;
}
//邻接点
public class ArcNode
{
	//邻接点序号
	public int AdjVex;
	//下一个邻接点
	public ArcNode Next;
}
